#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

//https://leetcode.cn/problems/palindrome-linked-list/submissions/

typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;

bool chkPalindrome(struct ListNode* A) {

    //找中间(或中间偏右)位置
    struct ListNode *slow = A;
    struct ListNode *fast = A;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }

    //将后半部分逆序
    struct ListNode *cur1 = A;
    struct ListNode *cur2 = slow;
    struct ListNode *prev = NULL;
    struct ListNode *next = slow->next;
    while (cur2) {
        next = cur2->next;
        cur2->next = prev;
        prev = cur2;
        cur2 = next;
    }

    //比较两部分
    cur2 = prev;
    while (cur2) {
        if (cur1->val != cur2->val) {
            return false;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return true;
}

int main() {

    return 0;
}